/*
 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package std.core;

// NOTE: autogenerated file

% template = ERB.new(File.read("Array_header.erb"), nil, '%', eoutvar: '_sub04')
<%= template.result(binding) %>

// Range is [startIndex, endIndex), i.e. startIndex included and endIndex is excluded
function checkRange(arrLen: int, startIndex: int, endIndex: int): boolean {
    // Since mostly everywhere for loop is used from startIndex till endIndex exclusive,
    // startIndex <= endIndex is used to cover empty array case
    return ((0 <= startIndex) && (startIndex <= endIndex) && (endIndex <= arrLen));
}

native function __alloc_array<T>(len: int, ofType: Object | null): T[]

class BuiltinArrayKeysIterator implements IterableIterator<number> {
    private len: int
    private idx: int = 0

    constructor(len: int) {
        this.len = len
    }

    override next(): IteratorResult<number> {
        if (this.idx >= this.len) {
            return new IteratorResult<number>()
        }
        return new IteratorResult<number>(this.idx++ as number)
    }

    override $_iterator(): IterableIterator<number> {
        return this
    }
}

% require 'ostruct'
% ctx = OpenStruct.new
% $ctx = ctx
% ctx.this = 'self'
% ctx.this_len_int = 'self.length'
% ctx.array_len_int = Proc.new { |v| "#{v}.length" }
% ctx.access_public = 'export function'
% ctx.access_private = 'function'
% ctx.override = ''
% ctx.get_unsafe = Proc.new { |t, i| "#{t}[#{i}]" }
% ctx.set_unsafe = Proc.new { |t, i, v| "#{t}[#{i}] = #{v}" }
% ctx.arr_method_call = Proc.new { |t, f| "#{f}(#{t}, " }
% primitive_types = ['boolean', 'byte', 'short', 'int', 'long', 'float', 'double', 'char']
% # NOTE(kprokopenko): primitive_types + ['T']
% (primitive_types).each { |el_type|
%   ctx.this_type = "#{el_type}[]"
%   ctx.this_arg = "self: #{ctx.this_type}, "
%   ctx.this_return_type = ctx.this_type
%   ctx.el_type = el_type
%   ctx.el_type_boxed = el_type[0].upcase + el_type[1..]
%   ctx.clone_this = 'cloneArray(self)'
%   ctx.make_buffer = Proc.new { |l, elt|
%     elt ||= ctx.el_type
%     if elt == 'T'
%       "__alloc_array<#{elt}>(#{l}, self)"
%     elsif elt == 'U'
%       "__alloc_array<#{elt}>(#{l}, null)"
%     else
%       "new #{elt}[#{l}]"
%     end
%   }
%   ctx.from_buffer = Proc.new { |b, elt| b }
%   ctx.array_of_type = Proc.new { |t| "#{t}[]" }
%   ctx.this_generic = ''
%   ctx.this_generic_one = ''
%   ctx.this_iterator_generic = ''
%   if el_type == 'T'
%     ctx.this_generic = '<T>'
%     ctx.this_iterator_generic = '<T>'
%     ctx.this_generic_one = 'T, '
%   end
% ctx.this_call = Proc.new { |f| "#{f}#{ctx.this_generic}(self, " }
function cloneArray<%= ctx.this_generic %>(self: <%= ctx.this_type %>): <%= ctx.this_type %> {
    const ret = <%= ctx.make_buffer.('self.length') %>;;
    for (let i = 0; i < self.length; i++) {
        ret[i] = self[i];
    }
    return <%= ctx.from_buffer.('ret') %>;
}
% template = ERB.new(File.read("Array_common.erb"), nil, '%', eoutvar: '_sub01')
<%= template.result(ctx.instance_eval { binding }) %>
% template = ERB.new(File.read("Array_map.erb"), nil, '%', eoutvar: '_sub02')
% primitive_types.each { |mapped|
%   ctx.mapped_type = mapped
%   ctx.map_generic = ctx.this_generic
<%# template.result(ctx.instance_eval { binding }) %>
% }

% ctx.mapped_type = ctx.el_type
% ctx.map_generic = ctx.this_generic
<%= template.result(ctx.instance_eval { binding }) %>

% ctx.mapped_type = 'U'
% ctx.map_generic = "<#{ctx.this_generic_one}U>"
<%# template.result(ctx.instance_eval { binding }) %>

/**
 * Constructs a new `Array` instance and populates it with
 * portion of a given array, filtered down to just the elements from the
 * given array that pass the test implemented by the provided function.
 *
 * @param fn test function, applied to each element of an array.
 *
 * @returns New `Array` instance constructed from `this` with elements filtered using test function `fn`.
 */
export function filter<%= ctx.this_generic %>(<%= ctx.this_arg %>fn: (v: <%= ctx.el_type %>, k: number) => boolean): <%= ctx.this_type %> {
    const mask = new boolean[<%= ctx.this_len_int %>]
    let cnt = 0

    for (let i: int = 0; i < <%= ctx.this_len_int %>; i++) {
        const val = self[i];
        if (fn(val, i)) {
            mask[i] = true
            cnt++;
        }
    }
    const res = <%= ctx.make_buffer.('cnt') %>;
    let idx_store = 0;
    for (let i: int = 0; i < <%= ctx.this_len_int %>; i++) {
        if (mask[i]) {
            res[idx_store++] = self[i]
        }
    }
    return <%= ctx.from_buffer.('res') %>;
}

export function concat<%= ctx.this_generic %>(self: <%= ctx.this_type %>, fst: <%= ctx.this_type %>, ...more: <%= ctx.this_type %>[]): <%= ctx.this_type %> {
    const lnMin = self.length + fst.length;
    let ln = lnMin;
    for (let i = 0; i < more.length; i++) {
        ln += more[i].length
    }
    const r = <%= ctx.make_buffer.('ln', ctx.el_type) %>;
    try {
        copyTo(self, r, 0, 0, self.length);
        copyTo(fst, r, self.length, 0, fst.length);
        let idx = lnMin;
        for (let i = 0; i < more.length; i++) {
            copyTo(more[i], r, idx, 0, more[i].length);
            idx += more[i].length;
        }
    } catch (e) {
        // impossible
    }
    return <%= ctx.from_buffer.('r') %>
}

/**
 * Reorders elements of `this` using comparator function.
 *
 * @param comparator function that defines the sort order.
 *
 * @note Mutating method
 */
export function sort<%= ctx.this_generic %>(<%= ctx.this_arg %>comparator: (a: <%= ctx.el_type %>, b: <%= ctx.el_type %>) => number): <%= ctx.this_return_type %> {
%   sort_elem_type = ctx.el_type == 'T' ? 'NullishType' : ctx.el_type
%   from_sort_elem_type = ctx.el_type == 'T' ? ' as T' : ''
    sort_subarray(self<%= ctx.el_type == 'T' ? ' as NullishType[]' : '' %>, 0, self.length, (l: <%= sort_elem_type %>, r: <%= sort_elem_type %>): boolean => {
        return comparator(l<%= from_sort_elem_type %>, r <%= from_sort_elem_type %>) < 0;
    });
    return self;
}

/**
 * Reorders elements of `this` using comparator function.
 *
 * @param comparator function that defines the sort order.
 *
 * @note Mutating method
 */
export function sort<%= ctx.this_generic %>(<%= ctx.this_arg %>): <%= ctx.this_return_type %> {
% if !primitive_types.include?(ctx.el_type)
    sort_subarray(self<%= ctx.el_type == 'T' ? ' as NullishType[]' : '' %>, 0, self.length, (l: <%= sort_elem_type %>, r: <%= sort_elem_type %>): boolean => {
        return new String(l).compareTo(new String(r)) < 0;
    });
% else
    sort(self, 0, self.length);
% end
    return self;
}

export function keys<%= ctx.this_generic %>(self: <%= ctx.this_type %>): IterableIterator<number> {
    return new BuiltinArrayKeysIterator(self.length);
}

%   template = ERB.new(File.read("Array_common_top_scope.erb"), nil, '%', eoutvar: '_sub03')
<%= template.result(ctx.instance_eval { binding }).gsub(/[ \t]+$/, '') %>

% }

function builtin_insertion_sort<T>(arr: T[], startIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i];
        if (comp(tmp, arr[startIndex]) as int < 0) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let j = i - 1;
            while (comp(tmp, arr[j]) as int < 0) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = tmp;
        }
    }
}

function perform_merge<T>(arr: T[], startIndex: int, midIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    const len1 = midIndex - startIndex + 1;
    const len2 = endIndex - midIndex;
    let left = new T[len1];
    let right = new T[len2];
    for (let i = 0; i < len1; i++) {
        left[i] = arr[startIndex + i];
    }
    for (let i = 0; i < len2; i++) {
        right[i] = arr[midIndex + 1 + i];
    }
    let i = 0;
    let j = 0;
    let k = startIndex;
    while (i < len1 && j < len2) {
        if (comp(left[i], right[j]) as int <= 0) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < len1) {
        arr[k] = left[i];
        k++;
        i++;
    }
    while (j < len2) {
        arr[k] = right[j];
        k++;
        j++;
    }
}

export function sort_stable<T>(arr: T[], startIndex: int, endIndex: int, comp: (lhs: T, rhs: T) => number): void {
    if (endIndex <= startIndex) {
        return;
    }

    const INS_SORT_DELTA = 16
    for (let i = startIndex; i < endIndex; i += INS_SORT_DELTA ) {
        builtin_insertion_sort<T>(arr, i, min(i + INS_SORT_DELTA , endIndex), comp)
    }
    if ((endIndex - startIndex) < INS_SORT_DELTA) {
        return;
    }
    for (let size = INS_SORT_DELTA; size < endIndex; size = 2 * size) {
        for (let left = startIndex; left < endIndex; left += 2 * size) {

            // Find ending point of left subarray and right subarray
            const mid = min(left + size - 1, endIndex - 1);
            const right = min((left + 2 * size - 1), (endIndex - 1));

            // Merge sub array arr[left.....mid] and arr[mid+1....right]
            if (mid < right) {
                perform_merge(arr, left, mid, right, comp);
            }
        }
    }
}

function defaultComparatorStr(a: String, b: String): number {
    return a.compareTo(b)
}

type buffStr = String | null
function stringified_insertion_sort<T>(arr: T[], arrStr: buffStr[], startIndex: int, endIndex: int): void {
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        const tmpStr = arrStr[i];
        if (defaultComparatorStr(tmpStr!, arrStr[startIndex]!) < 0) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
                arrStr[j] = arrStr[j - 1]
            }
            arrStr[startIndex] = tmpStr
            arr[startIndex] = tmp
        } else {
            let j = i - 1;
            while (defaultComparatorStr(tmpStr!, arrStr[j]!) < 0) {
                arr[j + 1] = arr[j];
                arrStr[j + 1] = arrStr[j]
                j--;
            }
            arr[j + 1] = tmp;
            arrStr[j + 1] = tmpStr
        }
    }
}

function stringified_perform_merge<T>(arr: T[], arrStr: buffStr[], startIndex: int, midIndex: int, endIndex: int): void {
    const len1 = midIndex - startIndex + 1;
    const len2 = endIndex - midIndex;
    type buffType = T | null
    let left = new buffType[len1]
    let right = new buffType[len2]
    let leftStr = new buffStr[len1]
    let rightStr = new buffStr[len2]
    for (let i = 0; i < len1; i++) {
        left[i] = arr[startIndex + i]
        leftStr[i] = arrStr[startIndex + i]
    }
    for (let i = 0; i < len2; i++) {
        right[i] = arr[midIndex + 1 + i]
        rightStr[i] = arrStr[midIndex + 1 + i]
    }
    let i = 0;
    let j = 0;
    let k = startIndex;
    while (i < len1 && j < len2) {
        if (defaultComparatorStr(leftStr[i]!, rightStr[j]!) <= 0) {
            arr[k] = left[i]!;
            arrStr[k] = leftStr[i]!;
            i++;
        } else {
            arr[k] = right[j]!;
            arrStr[k] = rightStr[j]!;
            j++;
        }
        k++;
    }
    while (i < len1) {
        arr[k] = left[i]!;
        arrStr[k] = leftStr[i]!;
        k++;
        i++;
    }
    while (j < len2) {
        arr[k] = right[j]!;
        arrStr[k] = rightStr[j]!;
        k++;
        j++;
    }
}

export function sort_default<T>(arr: T[], arrStr: buffStr[], startIndex: int, endIndex: int): void {
    if (endIndex <= startIndex) {
        return;
    }
    const INS_SORT_DELTA = 16
    for (let i = startIndex; i < endIndex; i += INS_SORT_DELTA ) {
        stringified_insertion_sort<T>(arr, arrStr, i, min(i + INS_SORT_DELTA , endIndex))
    }

    if ((endIndex - startIndex) < INS_SORT_DELTA) {
        return;
    }
    for (let size = INS_SORT_DELTA; size < endIndex; size = 2 * size) {
        for (let left = startIndex; left < endIndex; left += 2 * size) {

            // Find ending point of left subarray and right subarray
            const mid = min(left + size - 1, endIndex - 1);
            const right = min((left + 2 * size - 1), (endIndex - 1));

            // Merge sub array arr[left.....mid] and arr[mid+1....right]
            if (mid < right) {
                stringified_perform_merge(arr, arrStr, left, mid, right);
            }
        }
    }
}
